package graph;

import java.io.ObjectInputStream;
import java.util.*;

public class Graph{
    public static void main(String[] args) {
        Graph g = new Graph(5);
        String[] str = new String[]{"A","B","C","D","E"};
        for(String s :str)
            g.insert(s);
            g.add(0,1);
        g.add(0,2);
        g.add(1,3);
        g.add(1,4);
        g.add(1,2);
//        g.show();
        g.BFS();
    }
    private int[][] edges;//存储对应的邻节矩阵
    private List<String> vertex;  //存储顶点集合
    private int numOfEdges;//边的个数
    private boolean[] isVisited;
    Stack<Object> stack ;
    LinkedList link = new LinkedList();
    //构造器初始化矩阵大小
    Graph( int size){
        edges = new int[size][size];
        vertex = new ArrayList<String>(size);
        numOfEdges = 0;
        stack = new Stack<Object>();
    }

    /**
     * 深度优先遍历
     */
    public void DFS(){
        isVisited = new boolean[numOfEdges];
        for(int i =0;i<vertex.size();i++){
            if(!isVisited[i])
            DFS(0,isVisited);
        }

    }
    public void DFS(int num,boolean[] flag){
        System.out.println(num);
        flag[num]=true;
        int i =getFirstNeighbor(num);
        while (i!=-1){
            if(!flag[i]){
                DFS(i,flag);
            }
            i=getNextNeighbor(num,i);
        }
    }

    /**
     * 广度优先遍历
     */
    public void BFS(){
        isVisited = new boolean[numOfEdges];
        for(int i =0;i<vertex.size();i++){
            if(!isVisited[i]){
                BFS(0,isVisited);
            }

        }
    }
    public void BFS(int num,boolean[] flag){
       int u;
        int w;
        System.out.println(getVertex(num));
        flag[num]=true;
        link.addLast(num);
        while (!link.isEmpty()){
            u=(int)link.removeFirst();//出队列
            w=getFirstNeighbor(u);//获取u邻节点下标
        while (w!=-1){
            if(!flag[w]){
                System.out.println(getVertex(w));
                link.addLast(w);
                flag[w]=true;
            }
            w=getNextNeighbor(u,w);//获取下一个相邻字母
        }
        }
    }

    //根据前一个邻接结点的下标来获取下一个邻接结点
    public int getNextNeighbor(int v1,int v2){
        for(int i = v2+1;i<vertex.size();i++){
            if(edges[v1][i]>0){
                return i;
            }
        }
        return -1;
    }
    //得到第一个邻接结点的下标
    public int getFirstNeighbor(int i){
        for(int x=0;x<vertex.size();x++){
            if(edges[i][x]>0){
                return x;
            }
        }
        return -1;
    }
    //遍历图
    public void show(){
        System.out.println("  "+vertex);
        for(int i = 0;i<edges.length;i++){
            System.out.println(vertex.get(i)+" "+Arrays.toString(edges[i]));
        }
    }
    //获取角标对应的顶点
    public String getVertex(int i){
        return vertex.get(i);
    }
    //获取边的个数
    public int numberOfEdges(){
        return numOfEdges;
    }
    //插入顶点
    public void insert(String str){
        vertex.add(str);
    }
    /**
     *
     * @param x 表示点的下标
     * @param y 表示第几个顶点
     */ //添加边
    public void add(int x,int y){
            edges[x][y] = 1;
            edges[y][x] = 1;
            numOfEdges++;
    }
}